package com.lun.swordtowardoffer2.c15;

public class NumSimilarGroups {
	
	private static final FindCircleNum FCN = new FindCircleNum();

	public int numSimilarGroups(String[] A) {
		int[] fathers = new int[A.length];
		
		for(int i = 0; i < fathers.length; i++) {
			fathers[i] = i;
		}
		
		int groups = A.length;
		for(int i = 0; i < A.length;i++) {
			for(int j = i + 1; j < A.length; j++) {
				if(similar(A[i], A[j]) && FCN.union(fathers, i, j)) {
					groups--;
				}
			}
		}

		return groups;
	}

	private boolean similar(String str1, String str2) {
		
		int count = 0;
		
		for(int i = 0; i < str1.length();i++) {
			if(str1.charAt(i) != str2.charAt(i)) {
				count++;
			}
		}

		return count <= 2;
	}
	
}
